#include "LinkStack.h"
#include "LinkQueue.h"

int Partition(int *a, int start, int end)
{
    int left = start;
    int right = end;
    int temp = a[left];
    while (left < right)
    {
        while (a[right] > temp && left < right)
            right--;
        if (left < right)
            a[left++] = a[right];
        while (temp > a[left] && left < right)
            left++;
        if (left < right)
            a[right--] = a[left];
    }
    a[left] = temp;
    return left;
}
// 快速排序的非递归实现
void Fast_No_Recur(int *a, int start, int end)
{
    LinkStack s;
    // 把区间下标入栈
    s.Push((void *)(long)start);
    s.Push((void *)(long)end);

    while (!s.IsEmpty()) // 栈不为空：栈内存在未排序的区间
    {
        // 拿出区间
        long right = (long)*s.GetTop();
        s.Pop();
        long left = (long)*s.GetTop();
        s.Pop();

        // 分组排序
        long mid = Partition(a, left, right);
        if (left < mid - 1) // 左区间存在
        {
            // 左区间入栈
            s.Push((void *)(long)left);
            s.Push((void *)(long)(mid - 1));
        }
        if (mid + 1 < right) // 右区间存在
        {
            s.Push((void *)(long)(mid + 1));
            s.Push((void *)(long)right);
        }
    }
}

// int main(int argc, char *argv[])
// {
//     if(argc !=3)
//     {
//         std::cout<<"参数不对\n";
//         return -1;
//     }
//     //进制转换器
//     LinkStack s;
//     int num= std::atoi(argv[1]);
//     int n=std::atoi(argv[2]);
//     while(num != 0)
//     {
//         s.Push((void*)(long)(num % n));
//         num/=n;
//     }

//     while(!s.IsEmpty())
//     {
//         long number= (long)*s.GetTop();
//         if(number<=9)
//             std::cout<<number;
//         else
//             std::cout<<(char)(number-10+'a');
//         s.Pop();
//     }
//     std::cout<<std::endl;

//     return 0;

// int main()
// {
//     int a[] = {5, 4, 2, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1};
//     Fast_No_Recur(a, 0, 12);
//     for (int i = 0; i < 13; i++)
//     {
//         std::cout << a[i] << " ";
//     }
//     std::cout << std::endl;
//     return 0;
// }

int main()
{
    // 约瑟夫环

    LinkQueque q;
    for (int i = 0; i < 31; i++)
        q.Push((void *)(long)(i + 1));

    int count = 0;
    while (q.Size() > 1)
    {
        long number = (long)*q.GetFront();
        q.Pop();
        count++;
        if (count != 3)
        {
            q.Push((void *)number);
        }
        else
        {
            std::cout << number << "出局\n";
            count = 0;
        }
    }
    std::cout << (long)*q.GetFront() << "活了下来" << std::endl;
    return 0;
}